1. Field of the Invention
This invention relates to a data search method for reading a search object data one by one from a memory unit in which the search object data are specified and stored by address continuous in ascending order or descending order and an apparatus therefor. Specifically, in this search method and apparatus, processing for reading out a search object data from the memory unit and data comparison processing are optimized so that despite use of a memory having the same reading speed as a conventional one, as compared to a case in which the conventional binary search is used, entire processing time necessary for data search can be reduced.
2. Description of the Related Art
FIG. 1 shows a case that totally 2n+1 search object data having n+1 search address are stored in a memory unit in which they are specified by address continuous in ascending order or descending order. Respective data are stored in the order of data number in the same figure and in the order of their value from small to large or from large to small. Referring to FIG. 1, processing in binary search in which these search object data are read out successively and compared with comparison data provided as a search key will be described.
In the binary search, usually a search address of the first time is xe2x80x9c100000 . . . 0000xe2x80x9d indicated by the sign A1 in FIG. 1 which is in the center of continuous address space. As a next search address, any one of xe2x80x9c010000 . . . 000xe2x80x9d or xe2x80x9c110000 . . . 0000xe2x80x9d is selected depending on a result of comparison between data specified by the first time search address and comparison data given as a search key.
In the binary search, the search address space is divided to two parts with an address in the center of the search address as a boundary and data specified by this boundary address, namely, the search address is compared with the comparison data. Further, one of the divided address space is selected depending on a result of the comparison and the selected address space is set to next search address space. After that, the same processing is repeated with the center address in the search address space as a boundary. In the binary search, the search address space is divided to two parts successively and an object data is searched.
The binary search has been well known as a retrieval method for a large amount of data because the retrieval time for N data is proportional to log N.
FIG. 2 shows a structure of a conventional binary search apparatus. Here, an address setting device 1A is connected to a search object data storage unit 30 through an address bus 5. A search data register 22A of a data comparison unit 20A is connected to the search object data storage unit 30 through a data bus 7. The address setting device 10A outputs a search address in succession. The search object data storage unit 30 outputs stored search object data to the search data register 22A of the data comparison unit 20A according to the search address. The data comparison unit 20A compares this search object data in the search data register 22A with comparison data for search preliminarily set in the comparison data register 24A. A search of one time comprises a processing for reading the search object data from the search object data storage unit 30 according to the search address and a processing for comparing the read search object data with the comparison data as shown in FIG. 3. These processings are carried out alternately and repeatedly. If both the data do not coincide with each other as a result of the comparison, a next search address is set according to which is larger. After that, these processings are repeated until the search object data coincides with the comparison data. Here, if it is assumed that the times for reading and comparison are the same and the time is Ct, an entire processing time can be expressed by a following expression (1).
T=2xc3x97Ctxc3x97log Nxe2x80x83xe2x80x83(1) 
FIG. 4 shows the reading processing and comparison processing separately.
In the data comparison unit 20A, the reading processing is not carried out as shown by a broken line of FIG. 4 in a period of the processing for comparing data in the search data register 22A with data in the comparison data register 24A. On the other hand, the comparison processing is not carried out as shown by a broken line of the same Figure in a period of the processing for reading from the search object data storage unit 30 to the search data register 22A according to the search address from the address setting device 10A. As described above, the search object data storage unit 30 and data comparison unit 20A are not actuated in a half period of the processing time required for the search. Further, the period in which they are not actuated occupies a large weight in the search processing time.
Further, as the other search method than the above described binary search method, multiple division search in which a search object area is divided to more than two can be considered. In this case, by carrying out comparisons on multiple data read from multiple divided regions at the same time, the time required for the search can be reduced. For example, the number of divisions is set to M=2m and totally M data are read one by one in succession from each region. Next, if the read M data are compared at the same time, a processing for a single search requires M+1 cycle. Therefore, the processing time Ta required until the search is completed can be expressed as follows.                                                                         T                ⁢                                  xe2x80x83                                ⁢                a                            =                                                (                                      M                    +                    1                                    )                                xc3x97                C                ⁢                                  xe2x80x83                                ⁢                t                xc3x97                log                ⁢                                  xe2x80x83                                ⁢                                  N                  /                  m                                                                                                        =                                                                    (                                          M                      +                      1                                        )                                    /                  m                                xc3x97                C                ⁢                                  xe2x80x83                                ⁢                t                xc3x97                log                ⁢                                  xe2x80x83                                ⁢                N                                                                        (        2        )            
If a ratio (R of a following expression) between the processing time T of the aforementioned binary search and processing time Ta for multiple division search is less than 1, it can be said that the processing time has been reduced.                                                         R              =                              T                ⁢                                  xe2x80x83                                ⁢                                  a                  /                  T                                                                                                        =                                                                    (                                          M                      +                      1                                        )                                    /                  m                                xc3x97                C                ⁢                                  xe2x80x83                                ⁢                t                xc3x97                log                ⁢                                  xe2x80x83                                ⁢                                  N                  /                  2                                xc3x97                C                ⁢                                  xe2x80x83                                ⁢                t                xc3x97                log                ⁢                                  xe2x80x83                                ⁢                N                                                                                        =                                                                    (                                          M                      +                      1                                        )                                    /                  m                                /                2                                                                        (        3        )            
Because the number of divisions is more than two in the expression (3) above, Mxe2x89xa74, mxe2x89xa72. Therefore, R is 1.25 even if it is minimum, so that the multiple division search takes longer than the binary search. In the multiple division search described above, the number of comparison decreases as compared to the binary search and the frequency of data read increases, so that the entire processing time is extended.
Accordingly, the present invention has been achieved to solve the above problems and therefore, an object of the invention is to provide a data search method and an apparatus therefor capable of improving a processing speed and reducing an entire processing time required for data search as compared to a conventional binary search by optimizing a processing for reading search object data from a storage unit and a processing for data comparison even if a memory having the same reading speed as a conventional one is used.
Although the memory mentioned here refers to a general single port memory, it is not restricted thereto but a multi-port memory like a 2-port memory may be used. The single port memory refers to a general memory in which a pair of word line and bit line are provided for each memory cell of an incorporated memory cell matrix. The 2-port or multi-port memory refers to a specific memory in which by selecting two pairs or a plurality of the word lines at the same time, simultaneous access is enabled to different incorporated memory cells.
To achieve the above object, the present invention provides a binary search method in which search object data is stored in a storage unit according to continuous address in ascending order or descending order, the search object data is read out in succession and compared with comparison data given as a search key, the search object data being classified to data belonging to odd address and data belonging to even address in continuous addresses, allocated to two storage units and stored therein. When the search object data is read out, as corresponding two search addresses, an odd address and even address are specified at the same time and the readout thereof to the storage units are carried out at the same time. In parallel to this processing, the comparison of the previously read out data is carried out. As a result, idle time for access to the storage units and data comparison is eliminated thereby reducing the processing time required for the search.
Further from another aspect of the present invention, there is provided a binary search apparatus wherein search object data is stored in a storage unit according to continuous address in ascending order or descending order, the search object data is read out in succession and compared with comparison data given as a search key, the binary search apparatus comprising:
a data comparison unit for carrying out the comparison; an address setting unit for setting two addresses having different least significant bits (LSB) upon reading the search object data in succession, the search object data is classified to the data belonging to the odd address and the data belonging to the even address in the continuous addresses; a first storage unit for storing the data belong to the odd address; and a second storage unit for storing the data belonging to the even address. When the search object data is read out, as corresponding two search addresses, an odd address and even address are specified at the same time and the readout thereof to the first storage unit and second storage unit are carried out at the same time. Then, the previously read search object data and comparison data are compared with each other by the data comparison unit. As a result, the idle time for the access to the storage units is reduced thereby the processing time required for the search being also reduced.
Further, according to still another aspect of the present invention, there is provided a multiple division search method in which search object data is stored in storage units according to continuous address in ascending order or descending order, the search object data is read out in succession and compared with comparison data given as a search key, the search object data being allocated and stored in 2n different storage units, where nxe2x89xa72, in succession in the order of the continuous addresses. Then, when a plurality of the search object data are read out in succession, the addresses of the search object data are specified to the plurality of the storage units in which those data are stored at the same time and the search object data are read out at the same time. As a result, the processing time required for the search is reduced by simultaneous access to the plurality of the storage units.
Further, according to a further aspect of the present invention, there is provided a multiple division search apparatus wherein search object data stored in a storage unit according to continuous addresses in ascending order or descending order is read out in succession and compared with comparison data given a search key, the multiple division search apparatus comprising:
a data comparison unit for carrying out the comparison; an address setting unit for setting an address so that the storage unit from which each data is to be read out differs upon reading out a plurality of the search object data; and different storage units of power of two more than four in which the search object data are allocated and stored in the order of the continuous addresses. When the search object data are readout, the search addresses corresponding to the plurality of the storage units are specified and then the search data are read out at the same time. As a result, the processing time required for the search is reduced by the simultaneous access to the plurality of the storage units.
Hereinafter, the present invention will be described simply with reference to FIG. 1.
As an example, it is presumed that the search object data coinciding with the comparison data given as a search key is stored in a memory area specified by a search address of xe2x80x9c000000 . . . 0011xe2x80x9d of FIG. 1. In this case, the comparison data is stored in the comparison data register 24A. Generally, according to the conventional binary search, the search object data is read out in succession in the order of the following search addresses and the comparison data given as a search key is compared with the read out data to see which is large or whether they coincides with each other.
First step: xe2x80x9c100000 . . . 0000xe2x80x9d (even address)xe2x80x94A1 of FIG. 1
Second step: xe2x80x9c0100000 . . . 0000xe2x80x9d (even address)xe2x80x94A2 of FIG. 1
Third step: xe2x80x9c001000 . . . 0000xe2x80x9d (even address)
Fourth step: xe2x80x9c0001000 . . . 0000xe2x80x9d (even address)
As shown above, the search addresses from the first step to the fourth step are all the even address and generally, the search address before reading out the final search object data is even address. Then, only the readout of the last search object data is carried out by the odd address. Further, the address adjacent to the search address of each step is odd address.
According to the conventional binary search, the readout of the search object data from the storage unit is not carried out until a next address is determined by a result of the comparison between the search object data output by the previous readout and comparison data. Further, the search object data read oat is single. However, from the search address of the read out search object data, it is made evident that there are two candidates intended to be read out next time (not determined) before the search object data is compared with the comparison data. That is, when the address space of object for search is divided into two address spaces by a current search address, addresses located respectively in the centers of the two address spaces become candidates. That is, it is made evident that the next search address is any one of the two candidates before the comparison of the previous search object data. Therefore, by specifying the two candidate addresses of objects for a next search and reading out the search object data in parallel to this data comparison processing, it can be expected that the processing speed is improved twice as compared to the conventional processing speed. However, because the search object data are stored in the same memory according to the conventional binary search, the simultaneous readout is disabled. If data storage can be set so that the search object are stored in different memory banks and the same bank is not accessed at the same time, such simultaneous readout is enabled.
Then, the binary search method and binary search apparatus of the present invention have been achieved by noticing that the search addresses are arranged alternately in terms of odd and even and the search address of each step is even address until the last search, as described above. That is, any one of two addresses (even) of candidates for a next read out is changed (slid) to an adjacent odd address and further the memory is divided to two banks which are odd address group and even address group. In this way, the candidates for the next search come to belong to the odd bank and even bank each. The search object data are classified to data specified by the odd address and data specified by the even address according to continuous addresses in ascending order or descending order and further allocated to the odd bank and even bank, and then stored therein. Therefore, by specifying odd address and even address of a next search object data, these two memory banks are accessed at the same time so as to enable simultaneous reading out. Further, by reading out data specified by a search address of a candidate for a next search at the same time during comparison of the previously read two search object data, the comparison processing and data readout processing can be carried out continuously (FIG. 6). Thus, an entire processing time required for the binary search can be reduced despite use of a memory having the same reading speed as the conventional one.
Next, the multiple division search method and apparatus therefor of the present invention will be described. As described above, in the multiple division search method in which data is read out in succession from each of the multiple divided storage regions and compared at the same time, the entire processing time is extended as compared to the conventional binary search. In the multiple division search method and apparatus therefor of the present invention, reads of a plurality of data upon a single comparison are carried out at the same time, so as to reduce the processing time required for the search. Further, because the data to be read at the same time are stored in different storage units, no expensive memory such as a 2-port memory or multi-port memory is needed.
In the multiple division search method and apparatus therefor of the present invention, the search object data are allocated and stored in 2n different storage units, where nxe2x89xa72, in the order of continuous addresses. As a result, a search object data corresponding to a search address and a search object data corresponding to an address adjacent to the search address are stored in different storage units. Therefore, according to the same concept as the address setting in the even bank and odd bank by the binary search method, a plurality of the search addresses which are candidates for next readout are changed (slid) so that the plurality of the search object data can be read out from each different storage unit at the same time.
As described above, according to the multiple division search method, as compared to the conventional binary search, the frequency of comparison can be reduced and further, the number of the readout of the search object data can be reduced, so that the processing time required for the search can be also reduced.
The present invention do not restrict a concrete method for changing the search address such as the above described method. For example, the search address may be generated logically by arithmetic operation. Or it is permissible to change the search address by using any conversion table. Further, the present invention do not restrict the order of the search addresses to be generated by such a change indicated by a search tree to any particular one.